package top.ivansong92.example.leetcode.learning.common.algorithms;

import org.junit.Test;

import java.util.*;

public class Example {

    @Test
    public void testGetOrderOfMinglishAlphabet() {
        System.out.println(getOrderOfMinglishAlphabet(new String[]{"ba", "ad", "cd", "ca", "eb", "ed"}));
    }

    public String getOrderOfMinglishAlphabet(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        List<Character> alphabet = new ArrayList<>();
        Map<Character, Set<Character>> headerChMap = new HashMap<>();
        Map<Character, Set<Character>> trailChMap = new HashMap<>();
        alphabet.add(words[0].charAt(0));
        for (int i = 1; i < words.length; i++) {
            String last = words[i - 1];
            String current = words[i];
            if (current.charAt(0) != last.charAt(0)) {
                alphabet.add(current.charAt(0));
            }

            if (last.length() == 1 || current.charAt(0) != last.charAt(0)) {
                continue;
            }

            for (int j = 1; j < last.length() && j < current.length(); j++) {
                char a1 = last.charAt(j);
                char a2 = current.charAt(j);
                if (a1 != a2) {
                    if (a2 == alphabet.get(0)) {//比当前头部更靠前
                        alphabet.add(0, a1);
                    } else if (a1 == alphabet.get(alphabet.size() - 1)) {//比当前尾部更靠后
                        alphabet.add(a2);
                    } else {
                        headerChMap.computeIfAbsent(a1, HashSet::new).add(a2);
                        trailChMap.computeIfAbsent(a2, HashSet::new).add(a1);
                    }
                    break;
                }
            }
        }
        int index = 1;
        while (!headerChMap.isEmpty() && !trailChMap.isEmpty()) {
            if (index >= alphabet.size()) {
                break;
            }

            Character last = alphabet.get(index - 1);
            Set<Character> headerSet = headerChMap.get(last);

            Character current = alphabet.get(index);
            Set<Character> trailSet = trailChMap.get(current);
            if (headerSet == null || trailSet == null ||
                    headerSet.isEmpty() || trailSet.isEmpty()) {
                index++;
                continue;
            }

            Character matchCh = null;
            for (Character ch : headerSet) {
                if (trailSet.contains(ch)) {
                    matchCh = ch;
                    break;
                }
            }
            if (matchCh == null) {
                headerSet.remove(matchCh);
                trailSet.remove(matchCh);
                headerSet = headerChMap.get(matchCh);
                if (headerSet != null) {
                    headerSet.remove(last);
                }

                trailSet = trailChMap.get(matchCh);
                if (trailSet != null) {
                    trailSet.remove(current);
                }
                alphabet.add(index, matchCh);
            } else {
                index++;
            }
        }

        Character last = alphabet.get(alphabet.size() - 1);
        while (!headerChMap.isEmpty()) {
            Set<Character> headerSet = headerChMap.get(last);
            if (headerSet == null || headerSet.isEmpty()) {
                break;
            }
            last = new ArrayList<>(headerSet).get(0);
            alphabet.add(last);
        }

        char[] chars = new char[alphabet.size()];
        for (int i = 0; i < alphabet.size(); i++) {
            chars[i] = alphabet.get(i);
        }

        return new String(chars);
    }
}
